翻訳と辞書 Words near each other ・ Non-metallic inclusions ・ Non-methane volatile organic compound ・ Non-metropolitan county ・ Non-metropolitan district ・ Non-mevalonate pathway ・ Non-decimal currency ・ Non-deliverable forward ・ Non-denial denial ・ Non-denominated postage ・ Non-denominational ・ Non-denominational Muslim ・ Non-departmental public body ・ Non-Desarguesian plane ・ Non-destructive editing ・ Non-Detention Act ・ Non-deterministic Turing machine ・ Non-dialable point ・ Non-dictatorship ・ Non-diegetic insert ・ Non-difference (Abheda) ・ Non-dim circuit ・ Non-dimensionalization and scaling of the Navier–Stokes equations ・ Non-directional beacon ・ Non-disclosure agreement ・ Non-drying oil ・ Non-DVP ・ Non-economic damages caps ・ Non-English football clubs in the FA Cup ・ Non-English press of the Communist Party USA ・ Non-English press of the Socialist Party of America Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Non-deterministic Turing machine ： ウィキペディア英語版 Non-deterministic Turing machine In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers. In essence, ''a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules.'' It determines what action it should perform next according to its internal ''state'' and ''what symbol it currently sees''. An example of one of a Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', change it to 'B' and move left." In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation. By contrast, ''a non-deterministic Turing machine (NTM) may have a set of rules that prescribes more than one action for a given situation.'' For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left" and "If you are in state 2 and you see an 'A', change it to a 'C' and move right" in its rule set. A deterministic Turing machine (DTM) has a ''transition function'' that, for a given state and symbol under the tape head, specifies three things: * the symbol to be written to the tape, * the direction (left, right or neither) in which the head should move, and * the subsequent state of the finite control. For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5. A non-deterministic Turing machine (NTM) differs in that the state and tape symbol no longer ''uniquely'' specify these things; rather, ''many different actions may apply for the same combination of state and symbol.'' For example, an X on the tape in state 3 might now allow the NTM to write a Y, move right, and switch to state 5, ''or'' to write an X, move left, and stay in state 3. == Definition == A non-deterministic Turing machine can be formally defined as a 6-tuple $M=(Q,\; \backslash Sigma,\; \backslash iota,\; \backslash sqcup,\; A,\; \backslash delta)$, where * $Q$ is a finite set of states * $\backslash Sigma$ is a finite set of symbols (the tape alphabet) *$\backslash iota\; \backslash in\; Q$ is the initial state *$\backslash sqcup\; \backslash in\; \backslash Sigma$ is the blank symbol *$A\; \backslash subseteq\; Q$ is the set of accepting (final) states *$\backslash delta\; \backslash subseteq\; \backslash left(Q\; \backslash backslash\; A\; \backslash times\; \backslash Sigma\backslash right)\; \backslash times\; \backslash left(\; Q\; \backslash times\; \backslash Sigma\; \backslash times\; \backslash \; \backslash right)$ is a relation on states and symbols called the ''transition relation''. $L$ is the movement to the left, and $R$ is to the right. The difference with a standard (deterministic) Turing machine is that for those, the transition relation is a function (the transition function). Configurations and the ''yields'' relation on configurations, which describes the possible actions of the Turing machine given any possible contents of the tape, are as for standard Turing machines, except that the ''yields'' relation is no longer single-valued. The notion of string acceptance is unchanged: a non-deterministic Turing machine accepts a string if, when the machine is started on the configuration in which the tape head is on the first character of the string (if any), and the tape is all blank otherwise, at least one of the machine's possible computations from that configuration puts the machine into a state in $A$. (If the machine is deterministic, the possible computations are the prefixes of a single, possibly infinite, path.) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Non-deterministic Turing machine」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.